package sorting;

public class MergeSort
{
  public static void mergeSort(int[] input) {
    int[] temp = new int[input.length];
    recursiveMerge(input,temp,0,input.length - 1);
  }
  
  public static void recursiveMerge(int[] input, int[] temp, int startIndex,int endIndex) {
    if (startIndex < endIndex) {
      int center = (startIndex + endIndex) / 2;
      recursiveMerge(input,temp,startIndex,center);
      recursiveMerge(input,temp,center+1,endIndex);
      //merge the lists
      int left = startIndex;
      int right = center+1;
      
      for(int i=left;i<=endIndex;i++) {
        temp[i] = input[i];
      }
      int index = startIndex;
      while (index <= endIndex) {
       if (left <= center && right <= endIndex) {//both lists still have items remaining to merge
         if (temp[left] > temp[right]) {
           input[index] = temp[right];
           right++;
         } else {
           input[index] = temp[left];
           left++;
         }
         index++;
       } else { //one of the lists is out of items
         if (left<= center) {
           input[index] = temp[left];
           left++;
         } else {
           input[index] = temp[right];
           right++;
         }
         index++;
       }
      }
    } else {//base case
      return;
    }
  }
}
